package leetcode.Hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 * <p>
 * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/group-anagrams
 * @version 1.0
 * @date 2021/12/6 16:03
 * <p>
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 */
public class groupAnagrams {

    public static void main(String[] args) {

        System.out.println(groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
        System.out.println(groupAnagrams1(new String[]{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"}));
    }

    // 异位词 通过 Arrays.sort 得到的数组是一样的
    static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> anagramsMap = new HashMap<>();
        for (String str : strs) {
            String fixedStr = fixed(str);
            List<String> list = anagramsMap.getOrDefault(fixedStr, new ArrayList<>());
            list.add(str);
            anagramsMap.put(fixedStr, list);
        }
        return new ArrayList<>(anagramsMap.values());
    }

    static String fixed(String str) {
        char[] strChars = str.toCharArray();
        Arrays.sort(strChars);
        return new String(strChars);
    }

    // 构造一个质数数组，数组大小为26，每个质数表示一个字母
    static List<List<String>> groupAnagrams1(String[] strs) {
        HashMap<Long, List<String>> anagramsMap = new HashMap<>();
        // 26 个质数
        // 一个数乘2，在计算机中相当于给这个数左移一位（会在该二进制数尾部添一个零），如果给tip值一直乘2
        // （例如字符串为"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"），最后tip值会为0，导致错误，所以在质数数组中不使用2。
        // 链接：https://leetcode-cn.com/problems/group-anagrams/solution/javazhi-shu-xiang-cheng-fang-fa-yong-shi-5ms-ji-ba/

        // Integer[] prime = new Integer[]{
        //         2,  3,  5,  7,  11, 13, 17, 19, 23, 29,
        //         31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
        //         73, 79, 83, 89, 97, 101
        // };
        Integer[] prime = new Integer[]{
                3, 5, 7, 11, 13, 17, 19, 23, 29,
                31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                73, 79, 83, 89, 97, 101, 103
        };
        for (String str : strs) {
            Long key = 1L;
            for (char c : str.toCharArray()) {
                key *= prime[c - 'a'];
            }
            List<String> orDefault = anagramsMap.getOrDefault(key, new ArrayList<>());
            orDefault.add(str);
            anagramsMap.put(key, orDefault);
        }
        return new ArrayList<>(anagramsMap.values());
    }


}
